using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Linq.Dynamic;
using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0990. 等式方程的可满足性")]
    public class No0990_EquationsPossible : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Assert.TestExe(EquationsPossible, new string[] { "a==b", "b!=a" }, false);
            Assert.TestExe(EquationsPossible, new string[] { "b==a", "a==b" }, true);
            Assert.TestExe(EquationsPossible, new string[] { "a==b", "b==c", "a==c" }, true);
            Assert.TestExe(EquationsPossible, new string[] { "a==b", "b!=c", "c==a" }, false);
            Assert.TestExe(EquationsPossible, new string[] { "c==c", "b==d", "x!=z" }, true);
        }

        public bool EquationsPossible(string[] equations)
        {
            int[] parent = new int[26];
            for (int i = 0; i < 26; i++)
            {
                parent[i] = i;
            }
            foreach (string str in equations)
            {
                if (str[1] == '=')
                {
                    int index1 = str[0] - 'a';
                    int index2 = str[3] - 'a';
                    union(parent, index1, index2);
                }
            }
            foreach (string str in equations)
            {
                if (str[1] == '!')
                {
                    int index1 = str[0] - 'a';
                    int index2 = str[3] - 'a';
                    if (find(parent, index1) == find(parent, index2))
                    {
                        return false;
                    }
                }
            }
            return true;
        }

        private void union(int[] parent, int index1, int index2)
        {
            int find_index1 = find(parent, index1);
            int find_index2 = find(parent, index2);
            parent[find_index1] = find_index2;
        }

        private int find(int[] parent, int index)
        {
            while (parent[index] != index)
            {
                int par_value = parent[parent[index]];
                parent[index] = par_value;
                index = par_value;
            }
            return index;
        }
    }
}
